home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_10_08 / 1008108a < prev    next >
Encoding:
Text File  |  1992-06-02  |  10.1 KB  |  455 lines
  1.  
  2. /* ----------------------------------------------------------- */
  3.  
  4. #include <stdio.h>
  5. #include <string.h>
  6. #include <ctype.h>
  7. #include <stdlib.h>
  8.  
  9. typedef struct node {
  10.     char *pstring;
  11.     struct node *pleft_child;
  12.     struct node *pright_child;
  13. } Node;
  14.  
  15. #define EXIT 'E'
  16. #define HELP '?'
  17. #define ADD_NODE 'A'
  18. #define REMOVE_NODE 'R'
  19. #define DISPLAY_NODE 'D'
  20. #define PRINT_TREE 'P'
  21. #define COUNT_NODES 'C'
  22. #define FIND_DEPTH 'F'
  23.  
  24. void help(void);
  25. void add_node(Node **pproot_node);
  26. void remove_node(Node **pproot_node);
  27. void remove_node_1(Node *ploc_node, Node *pparent_node,
  28.     Node **pproot_node);
  29. void remove_node_2(Node *ploc_node, Node *pparent_node,
  30.     Node **pproot_node);
  31. void display_node(Node *proot_node);
  32. void print_tree(Node *proot_node);
  33. unsigned int count_nodes(Node *proot_node);
  34. unsigned int find_depth(Node *proot_node);
  35. Node *find_node(Node *proot_node, char *pstring,
  36.     Node **ppparent_node);
  37.  
  38. void push(Node *value);
  39. Node *pop(void);
  40.  
  41. Node *get_free_node(void);
  42. void put_free_node(Node *pnode);
  43.  
  44. /* ----------------------------------------------------------- */
  45.  
  46. main()
  47. {
  48.     int inchar = 'x';    /* force initial prompt */
  49.     int done = 0;
  50.  
  51.     static Node *proot_node = NULL;
  52.  
  53. /* ----------------------------------------------------------- */
  54.  
  55.     while (!done) {
  56.         if (inchar != ' ')
  57.             printf("\nEnter Action Code (%c for help): ", HELP);
  58.         switch(toupper(inchar = getchar())) {
  59.  
  60.     case EXIT:
  61.         done = 1;
  62.         break;
  63.  
  64.     default:
  65.         printf("\n   Invalid command. Please try again\n");
  66.         break;
  67.  
  68.     case HELP:
  69.         help();
  70.         break;
  71.  
  72.     case '\n':    /* ignore white space on input */
  73.     case ' ' :
  74.     case '\t':
  75.     case '\v':
  76.     case '\f':
  77.         inchar = ' ';    /* indicate white space input */
  78.         break;
  79.  
  80.     case ADD_NODE:
  81.  
  82.         add_node(&proot_node);
  83.         break;
  84.  
  85.     case REMOVE_NODE:
  86.  
  87.         remove_node(&proot_node);
  88.         break;
  89.  
  90.     case DISPLAY_NODE:
  91.  
  92.         display_node(proot_node);
  93.         break;
  94.  
  95.     case PRINT_TREE:
  96.  
  97.         print_tree(proot_node);
  98.         break;
  99.  
  100.     case COUNT_NODES:
  101.  
  102.         printf("\n   There are %u nodes\n", count_nodes(proot_node));
  103.         break;
  104.  
  105.     case FIND_DEPTH:
  106.  
  107.         printf("\n   Tree depth is %u\n", find_depth(proot_node));
  108.         break;
  109.  
  110.         }
  111.     }
  112.  
  113.     return (0);
  114. }
  115.  
  116. /* --------------------------------------------------------------
  117.  
  118. FUNCTION ADD_NODE: The steps to add a new node to the tree are:
  119.  
  120. A.  Get a string from the user.
  121.  
  122. B.  If this string already exists in the tree complain and get out.
  123.  
  124. C.  Have a unique string so get a free node from free node tree.  If
  125.     no more, complain and get out.
  126.  
  127. D.  Get space for new node's string.  If no more, complain and get
  128.     out.
  129.  
  130. E.  Initialize new node's string pointer and left and right child
  131.     pointers and copy user string to allocated space.
  132.  
  133. F.  If this is the root (first) node, initialize the the root pointer.
  134.  
  135. G.  Else if its string is less than that of the parent node, insert it 
  136.     as the left child of that node.
  137.  
  138. H.  Else, insert it as the right child of that node.
  139.  
  140. I.  And if the new node is inserted after the last node in the list,
  141.     adjust the tail pointer accordingly.
  142.  
  143. -------------------------------------------------------------- */
  144.  
  145. void add_node(Node **pproot_node)
  146. {
  147.     Node *pnew_node;    /* ptr to new node */
  148.     Node *ploc_node;    /* ptr to located node */
  149.     Node *pparent_node;    /* ptr to parent node */
  150.     char *pstring;        /* ptr to alloced string space */
  151.     char string[21];    /* tmp holder for node's string */
  152.  
  153. /*A*/    printf("\n   Enter new string: ");
  154.     scanf("%20s", string);
  155.  
  156. /*B*/    ploc_node = find_node(*pproot_node, string, &pparent_node);
  157.     if (ploc_node != NULL) {
  158.         printf("\n   Node already exists in tree\n");
  159.         return;
  160.     }
  161.  
  162. /*C*/    pnew_node = get_free_node();
  163.     if (pnew_node == NULL) {
  164.         printf("\n   No nodes available\n");
  165.         return;
  166.     }
  167.  
  168. /*D*/    pstring = malloc(strlen(string) + 1);
  169.     if (pstring == NULL) {
  170.         printf("\n   No string space available\n");
  171.         return;
  172.     }
  173.  
  174. /*E*/    pnew_node->pstring = pstring;
  175.     strcpy(pnew_node->pstring, string);
  176.     pnew_node->pleft_child = NULL;
  177.     pnew_node->pright_child = NULL;
  178.  
  179. /*F*/    if (pparent_node == NULL) {
  180.         *pproot_node = pnew_node;
  181.     }
  182. /*G*/    else if (strcmp(pstring, pparent_node->pstring) < 0) {
  183.         pparent_node->pleft_child = pnew_node;
  184.     }
  185. /*H*/    else {
  186.         pparent_node->pright_child = pnew_node;
  187.     }
  188.  
  189.     printf("\n   Node added\n");
  190. }
  191.  
  192. /* --------------------------------------------------------------
  193.  
  194. FUNCTION DISPLAY_NODE: The steps to display a node are:
  195.  
  196. A.  Complain if list empty.
  197.  
  198. B.  Get a string from the user.
  199.  
  200. C.  If no such node, complain and get out.
  201.  
  202. D.  Display node's string value.
  203.  
  204. E.  Say whether node is the root or has a parent.
  205.  
  206. F.  Say whether node has a left child.
  207.  
  208. G.  Say whether node has a right child.
  209.  
  210. -------------------------------------------------------------- */
  211.  
  212. void display_node(Node *proot_node)
  213. {
  214.     Node *pparent_node;    /* ptr to parent node */
  215.     Node *ploc_node;    /* ptr to located node */
  216.     char string[21];    /* tmp holder for node's string */
  217.  
  218. /*A*/    if (proot_node == NULL) {
  219.         printf("\n   Tree is empty\n");
  220.         return;
  221.     }
  222.  
  223. /*B*/    printf("\n   Enter node string to search for: ");
  224.     scanf("%20s", string);
  225.  
  226. /*C*/    ploc_node = find_node(proot_node, string, &pparent_node);
  227.     if (ploc_node == NULL) {
  228.         printf("\n   No such node exists\n");
  229.     }
  230.     else {
  231. /*D*/        printf("\n   Node %s found\n", ploc_node->pstring);
  232. /*E*/        if (pparent_node == NULL) {
  233.             printf("   This node is the tree root\n");
  234.         }
  235.         else {
  236.             printf("   This node's parent is %s\n",
  237.                 pparent_node->pstring);
  238.         }
  239.  
  240. /*F*/        if (ploc_node->pleft_child == NULL) {
  241.             printf("   This node has no left child\n");
  242.         }
  243.         else {
  244.             printf("   This node's left child is %s\n",
  245.                 ploc_node->pleft_child->pstring);
  246.         }
  247.  
  248. /*G*/        if (ploc_node->pright_child == NULL) {
  249.             printf("   This node has no right child\n");
  250.         }
  251.         else {
  252.             printf("   This node's right child is %s\n",
  253.                 ploc_node->pright_child->pstring);
  254.         }
  255.     }
  256. }
  257.  
  258. /* --------------------------------------------------------------
  259.  
  260. FUNCTION PRINT_TREE: The steps to display all nodes in the tree in
  261.     infix order are:
  262.  
  263. A.  Complain if tree empty.
  264.  
  265. B.  Initialize a pointer to the root of the tree.
  266.  
  267. C.  Push a null sentinel on the stack.
  268.  
  269. D.  Push the whole left subtree on the stack.
  270.  
  271. E.  Start backtracking by popping off last node pushed.
  272.  
  273. F.  Backtrack until we run into the sentinel placed on the stack in
  274.     Step B.
  275.  
  276. G.  Display node's value.
  277.  
  278. H.  If the current node has a right branch follow that branch and go
  279.     to Step C.
  280.  
  281. I.  Pop the next node off stack.
  282.  
  283. -------------------------------------------------------------- */
  284.  
  285. void print_tree(Node *proot_node)
  286. {
  287.     Node *pnode;
  288.     unsigned int count = 0;
  289.  
  290. /*A*/    if (proot_node == NULL) {
  291.         printf("\n   Tree is empty\n");
  292.         return;
  293.     }
  294.  
  295.     putchar('\n');
  296.  
  297. /*B*/    pnode = proot_node;
  298. /*C*/    push(NULL);
  299.  
  300. /*D*/
  301. loop:    while (pnode != NULL) {
  302.         push(pnode);
  303.         pnode = pnode->pleft_child;
  304.     }
  305.  
  306. /*E*/    pnode = pop();
  307. /*F*/    while (pnode != NULL) {
  308.         ++count;
  309. /*G*/        printf("%7u %-10s L: %-10s R: %-10s\n",
  310.             count, pnode->pstring,
  311.             (pnode->pleft_child != NULL)
  312.             ? pnode->pleft_child->pstring : "-",
  313.             (pnode->pright_child != NULL)
  314.             ? pnode->pright_child->pstring : "-");
  315.  
  316. /*H*/        if (pnode->pright_child != NULL) {
  317.             pnode = pnode->pright_child;
  318.             goto loop;
  319.         }
  320. /*I*/        pnode = pop();
  321.     }
  322. }
  323.  
  324. /* --------------------------------------------------------------
  325.  
  326. FUNCTION COUNT_NODES: The steps to count the number of nodes in the
  327.     tree are:
  328.  
  329. A.  If we've reached the end of a subtree, set count to zero.
  330.  
  331. B.  Otherwise, the total node count of the subtree from this node on 
  332.     down is the sum of the counts of the left and right subtrees plus 
  333.     1 for this (parent) node.
  334.  
  335. -------------------------------------------------------------- */
  336.  
  337. unsigned int count_nodes(Node *proot_node)
  338. {
  339. /*A*/    if (proot_node == NULL) {
  340.         return 0;
  341.     }
  342.  
  343. /*B*/    return (count_nodes(proot_node->pleft_child) + 
  344.         count_nodes(proot_node->pright_child) + 1);
  345. }
  346.  
  347. /* --------------------------------------------------------------
  348.  
  349. FUNCTION FIND_DEPTH: The steps to find the depth of the tree are:
  350.  
  351. A.  If we've reached the end of a subtree, set count to zero.
  352.  
  353. B.  Otherwise, find the depth of the left and right subtrees of this 
  354.     node.
  355.  
  356. C.  Return the larger of the left and right subtree depths adding 1 to 
  357.     account for the current node.
  358.  
  359. -------------------------------------------------------------- */
  360.  
  361. unsigned int find_depth(Node *proot_node)
  362. {
  363.     unsigned int left_depth;
  364.     unsigned int right_depth;
  365.  
  366. /*A*/    if (proot_node == NULL) {
  367.         return 0;
  368.     }
  369.  
  370. /*B*/    left_depth  = find_depth(proot_node->pleft_child);
  371.     right_depth = find_depth(proot_node->pright_child);
  372.  
  373. /*C*/    if (left_depth >= right_depth) {
  374.         return left_depth + 1;
  375.     }
  376.     else {
  377.         return right_depth + 1;
  378.     }
  379. }
  380.  
  381. /* --------------------------------------------------------------
  382.  
  383. FUNCTION FIND_NODE: The steps to find a node and its parent node are:
  384.  
  385. A.  If the root is empty we have no tree so there is no parent and no 
  386.     match.
  387.  
  388. B.  If the string matches that of the root there is is no parent and 
  389.     we return the root's address.
  390.  
  391. C.  Decide whether to go down the root's left or right child.
  392.  
  393. D.  Remember that root is the parent at this point.
  394.  
  395. E.  Do steps F-H until we get to the end of the path.
  396.  
  397. F.  If we have a match, save parent address and return address of 
  398.     match.
  399.  
  400. G.  Else, if string is less than current node's, set parent to current 
  401.     and follow left child.
  402.  
  403. H.  Else, set parent to current and follow right child.
  404.  
  405. I.  Have exhausted search so return last node as parent and indicate 
  406.     no match found.
  407.  
  408. -------------------------------------------------------------- */
  409.  
  410. Node *find_node(Node *proot_node, char *pstring,
  411.     Node **ppparent_node)
  412. {
  413.     int comp;        /* comparison flag */
  414.     Node *pnode;        /* used to traverse tree */
  415.     Node *psave_node;    /* used to keep track of parent */
  416.  
  417. /*A*/    if (proot_node == NULL) {
  418.         *ppparent_node = NULL;
  419.         return NULL;
  420.     }
  421.  
  422. /*B*/    if ((comp = strcmp(pstring, proot_node->pstring)) == 0) {
  423.         *ppparent_node = NULL;
  424.         return proot_node;
  425.     }
  426.  
  427. /*C*/    if (comp < 0) {
  428.         pnode = proot_node->pleft_child;
  429.     }
  430.     else {
  431.         pnode = proot_node->pright_child;
  432.     }
  433.  
  434. /*D*/    psave_node = proot_node;
  435.  
  436. /*E*/    while (pnode != NULL) {
  437. /*F*/        if ((comp = strcmp(pstring, pnode->pstring)) == 0) {
  438.             *ppparent_node = psave_node;
  439.             return pnode;
  440.         }
  441. /*G*/        else if (comp < 0) {
  442.             psave_node = pnode;
  443.             pnode = pnode->pleft_child;
  444.         }
  445. /*H*/        else {
  446.             psave_node = pnode;
  447.             pnode = pnode->pright_child;
  448.         }
  449.     }
  450.  
  451. /*I*/    *ppparent_node = psave_node;
  452.     return NULL;
  453. }
  454.  
  455.